3.4 Подбор гиперпараметров

Как эффективно подбирать значения гиперпараметров модели и не переобучиться при этом

Введение

Для начала поймём, в чём отличие параметров модели от гиперпараметров:

  • Параметры настраиваются в процессе обучения модели на данных. Например, веса в линейной регрессии, нейросетях, структура решающего дерева.

  • Гиперпараметры — это характеристики модели, которые фиксируются до начала обучения: глубина решающего дерева, значение силы регуляризации в линейной модели, скорость обучения (англ. learning rate) для градиентного спуска.

Рассмотрим, например, модель линейной регрессии:

f(X)=Xw,f(X) = Xw,

где

  • w=(w0,w1,...,wn)w = (w_0,\,w_1,\,...\,,w_n) — веса модели;

  • X=(xij)X = (x_{ij}) — матрица, в которой каждая строка содержит признаки одного объекта выборки (для удобства записи считаем, что первый столбец в этой матрице константный).

Эта модель может обучаться с помощью минимизации следующего функционала:

L=yXw2+Cw2,\mathcal{L} = \|y-Xw\|^2 + C\|w\|^2,

где

  • yy — целевая переменная;
  • CC — коэффициент регуляризации.

В процессе минимизации L\mathcal{L} веса ww настраиваются по обучающей выборке, то есть являются параметрами. В то же время величина коэффициента регуляризации задаётся до начала обучения, то есть она гиперпараметр.

image.png

Другой хороший пример — решающее дерево. Его гиперпараметры — это максимальная глубина дерева, критерий ветвления, минимальное число семплов в листе дерева и ещё много других. А параметр — сама структура решающего дерева: обучение состоит в том, чтобы на каждом уровне дерева выбрать, по какому признаку должно произойти ветвление и с каким пороговым значением этого признака.

Методы подбора гиперпараметров

Качество модели может очень сильно варьироваться в зависимости от гиперпараметров, поэтому существуют разнообразные методы и инструменты для их подбора.

При этом, вне зависимости от выбранного вами метода подбора гиперпараметров, оценку и сравнение моделей нужно проводить грамотно. Пусть у нас есть несколько моделей разной природы (метод ближайших соседей, случайный лес, логистическая регрессия) или несколько нейросеток с разными архитектурами. Для каждой из моделей нужно подобрать гиперпараметры, а затем сравнить между собой модели с наилучшими гиперпараметрами.

Есть два наиболее часто используемых варианта:

  • разделить выборку на тренировочную, валидационную и тестовую части;
  • провести кросс-валидацию.

Первый вариант

Если мы делим выборку только на тренировочную и тестовую части, в модель через подобранные гиперпараметры просачивается информация о тестовой выборке. Это означает, что на новых данных модели могут не сохранить свои качества и что их сравнение не будет честным.

Поэтому предлагается разделить выборку на тренировочную, валидационную и тестовую части, для каждой модели выбирать гиперпараметры, максимизирующие её метрики на валидации, а окончательное сравнение моделей проводить по тестовым метрикам.

image.png
Источник

Второй вариант

Провести кросс-валидацию.

Кросс-валидация может быть нужна в случаях, если данных мало или мы не хотим зависеть от конкретного выбора валидационного множества. Примерный алгоритм:

  • зафиксировать некоторое тестовое множество и отложить его;

  • разделить оставшееся множество данных на kk фолдов (подмножеств), пройтись по ним циклом, на каждой итерации фиксируя один фолд в качестве валидационного и обучаясь на остальных;

  • как оценку качества модели взять среднее значение валидационной метрики по фолдам;

  • финальное сравнение моделей с уже подобранными гиперпараметрами проводить на отложенном тестовом множестве.

image.png
Источник (в связи с ограничениями, установленными сервисом для пользователей на территории РФ, доступ к источнику может быть заблокирован или ограничен)

Подробное описание процесса сравнения моделей между собой можно найти в параграфах, посвящённых кросс-валидации и сравнению и оценке качества моделей.

Далее мы рассмотрим несколько методов подбора гиперпараметров для моделей и в конце приведём список библиотек для Python, в которых эти методы реализованы, а также сравним все описанные методы между собой.

Методы «на каждый день»

Самый естественный способ организовать перебор наборов гиперпараметров — сделать перебор по сетке (англ. Grid Search):

  • для каждого гиперпараметра фиксируется несколько значений;

  • перебираются все комбинации значений различных гиперпараметров, на каждой из этих комбинаций модель обучается и тестируется;

  • выбирается комбинация, на которой модель показывает лучшее качество.

Примеры:

  • для метода ближайших соседей можно, например, перебирать по сетке число соседей (скажем, от 1 до 20) и метрику, по которой будет измеряться расстояние между объектами выборки (евклидова, манхэттенская и так далее);

  • для решающих деревьев можно перебирать по сетке сочетания значений максимальной глубины дерева и различные критерии ветвления (критерий Джини, энтропийный критерий).

Перебор некоторых значений гиперпараметров можно вести по логарифмической шкале, так как это позволяет быстрее определить правильный порядок параметра и в то же время значительно уменьшить время поиска. Так можно подбирать, например, значение learning rate для градиентного спуска, значение константы регуляризации для линейной регрессии или метода опорных векторов (SVM).

Сразу же видно естественное ограничение этого метода: если комбинаций параметров слишком много либо каждое обучение/тест длится долго, алгоритм не завершится за разумное время.

Если у вас возникает очень большое количество комбинаций параметров, вы можете какими-то способами пытаться справляться с этой проблемой:

  • можно взять меньше значений каждого гиперпараметра, но тогда есть вероятность пропустить наилучшую комбинацию;

  • можно уменьшить число фолдов в кросс-валидации, но оценка параметров станет более шумной;

  • можно оптимизировать параметры последовательно, а не перебирать их комбинации, но снова есть вероятность получить неоптимальное решение;

  • можно перебирать не все комбинации гиперпараметров, а только случайное подмножество.

Последний способ называется случайным поиском по сетке (англ. Random Search). Для каждого гиперпараметра задаётся распределение, из которого выбирается его значение. Комбинация гиперпараметров составляется семплированием из этих распределений (хорошие советы по поводу выбора распределений можно найти в документации библиотеки sklearn).

Таким образом, благодаря случайному выбору очередной комбинации гиперпараметров вы можете найти оптимальную комбинацию за меньшее число итераций.

Это изображение хорошо иллюстрирует отличия поиска по сетке от случайного поиска:

image.png
Источник

То есть качество нашей модели в зависимости от гиперпараметров — это функция многих переменных с некоторой нетривиальной поверхностью. Но эта поверхность может зависеть от одной из своих переменных намного меньше, чем от другой. Если бы мы знали, какой гиперпараметр важнее для перформанса модели, мы бы рассмотрели больше его возможных значений, но часто у нас нет такой информации и мы рассматриваем некоторое наперёд заданное число значений для каждого гиперпараметра.

Метод Random Search может рассмотреть более разнообразные значения гиперпараметров за то же число итераций, что и Grid Search. Тем самым он с большей вероятностью найдёт те значения, которые сильнее всего влияют на качество модели, а значит, с большей вероятностью обнаружит наилучшую комбинацию значений гиперпараметров.

Есть ещё одно довольно интересное объяснение, почему Random Search работает хорошо. Рассмотрим случай, когда у нас конечная сетка гиперпараметров (каждому гиперпараметру соответствует конечное число значений).

В этой сетке выделим группу размером 5%5\% от общего числа наборов гиперпараметров, на которой модель достигает лучшего качества. Для этого можно мысленно отранжировать все наборы по качеству в некоторый список и взять топ-5%5\% этого списка).

Тогда некоторый набор гиперпараметров не попадает в эту группу с вероятностью 10,051 − 0,05. Если мы насемплировали nn наборов, то каждый из них не попал в эту группу с вероятностью (1  0,05)n(1 − 0,05)^n. И, соответственно, вероятность того, что хотя бы один насемплированный набор попал в лучшую группу, равна 1  (1  0,05)n1 − (1 − 0,05)^n. Мы можем решить неравенство

1(10,05)n0,951 − (1 − 0,05)^n \ge 0,95

и выяснить, что при n60n \ge 60 мы попадём в топ-5% с вероятностью не менее 0,950,95. Это в большинстве случаев значительно быстрее, чем перебор всех комбинаций гиперпараметров с помощью Grid Search.

Если в рассуждении выше у нас некоторым гиперпараметрам соответствует непрерывное распределение, то всегда можно предположить, что мы уже насемплировали из этих распределений некоторое конечное число значений (равное числу итераций Random Search), а дальше считать, что мы работаем с конечной сеткой.

Конечно, остаётся наша зависимость от самой сетки гиперпараметров, и не всякая сетка обязана содержать в себе глобальный максимум перформанса модели или даже гиперпараметры из интервала вокруг него.

Зафиксируем

Grid Search хорошо работает, когда у вас совсем мало гиперпараметров, либо вы смогли распараллелить его работу.

В защиту этого метода хочется сказать, что часто на практике приходится делать перебор гиперпараметров вообще вручную (если один инстанс вашей модели учится недели две и использует много ресурсов) либо по очень небольшой сетке. Так что метод вполне в ходу!

Random Search представляет собой небольшое усложнение относительно Grid Search, но при этом оказывается намного более эффективным.

Полезные ссылки

Продвинутые методы

Методы, которые мы рассмотрели до этого, — Grid Search и Random Search — являются отличной отправной точкой, но обладают одним существенным недостатком: они не используют результаты предыдущих итераций для принятия решения о том, какие гиперпараметры стоит попробовать следующими.

Иначе говоря, каждая новая попытка происходит с чистого листа, игнорирует уже полученный опыт.

Однако существуют более умные стратегии, которые стремятся не просто перебрать заданное пространство гиперпараметров, а целенаправленно исследовать те области, где, согласно накопленным данным, вероятность нахождения оптимального набора гиперпараметров наиболее высока. О них и пойдёт речь дальше в параграфе.

Не переживайте, если что-то останется непонятным! Это нормально: продвинутые методы часто требуют нескольких прочтений или практических экспериментов. Главное — помнить, что цель этого раздела — не заставить вас сразу стать экспертом, а дать ориентиры: почему эти методы могут быть полезны и когда стоит их применять.

Exploration vs exploitation

В машинном обучении достаточно часто встречаются такие термины, как exploration (изучение, исследование) и exploitation (применение). Суть этих терминов хорошо поясняет следующий пример из реальной жизни. Допустим, перед вами стоит выбор, в какой ресторан пойти сегодня. Пусть ваш любимый ресторан находится прямо за углом.

Вы ходите туда каждый день и поэтому достаточно уверены в том, насколько вкусным будет ваш обед. Но при этом не рассматриваете никакие другие опции и, вероятно, упускаете возможность поесть гораздо вкуснее в другом месте. Если же вы будете обедать каждый раз в новом месте, то очень часто будете не удовлетворены результатом.

image.png

В описанных далее методах подбора гиперпараметров так или иначе будет происходить поиск баланса между изучением и применением. Одно из основных отличий всех методов, которые будут описаны далее, от Grid Search и Random Search — возможность учитывать результаты предыдущих вычислений.

Соответственно, у нас есть две стратегии выбора точки для следующей итерации:

  • exploration: исследуем те области, в которых у нас мало семплов на текущей итерации. Это даёт нам возможность с меньшей вероятностью пропустить оптимальное значение.
  • exploitation: выбираем больше семплов в тех областях, которые мы достаточно неплохо изучили и где, как мы считаем, с большой вероятностью находится оптимум.

Байесовская оптимизация

Байесовская оптимизация — это итерационный метод, позволяющий оценить оптимум функции, не дифференцируя её. Кроме того, на каждой итерации метод указывает, в какой следующей точке мы с наибольшей вероятностью улучшим нашу текущую оценку оптимума. Это позволяет значительно сократить количество вычислений функции, каждое из которых может быть довольно затратным по времени.

Подбор гиперпараметров тоже можно сформулировать в виде задачи, которая может решаться с помощью байесовской оптимизации. Пусть, например, наша функция — значение валидационных метрик в зависимости от текущего сочетания гиперпараметров. Её вычисление затратно по времени (нужно натренировать и провалидировать модель), и мы не можем вычислить градиенты этой функции по её переменным (нашим гиперпараметрам).

Байесовская оптимизация имеет две основные компоненты:

  • вероятностную модель, которая приближает распределение значений целевой функции в зависимости от имеющихся исторических данных (часто в качестве такой модели выбирают гауссовские процессы);

  • функцию, которая позволяет по некоторым статистикам текущей вероятностной модели функции ff указать, в какой следующей точке нужно вычислить значение ff. Эта функция называется acquisition function. Она должна балансировать между exploration и exploitation в следующем смысле:

    • exploration — исследовать те точки, в которых дисперсия нашей вероятностной модели велика;

    • exploitation — исследовать те точки, где среднее нашей модели велико (и может служить оценкой максимума ff).

Пара слов о терминологии

На русский язык acquisition function можно перевести как «функция выгоды». Но это не сильно в ходу, в индустрии принято использовать англицизм.

Мы не будем отступать от этого правила.

Простой пример acquisition function — сумма среднего вероятностной модели и стандартного отклонения с некоторым весом:

α(x)=μ(x)+βσ(x),\alpha(x) = \mu(x) +\beta\sigma(x),

где xx — точка из пространства, в котором мы оптимизируем целевую функцию (в нашем контексте это вектор значений гиперпараметров). На картинке ниже изображены обе компоненты, из которых складывается данная acquisition function: среднее вероятностной модели μ\mu (синий график) и доверительный интервал, ширина которого в каждой точке пропорциональна стандартному отклонению вероятностной модели (жёлтая область).

Среднее модели μ\mu стремится приблизить искомую функцию ff и в точности равно ff в тех точках, где значения ff известны. Доверительный интервал имеет переменную ширину, так как чем дальше находится некоторая точка от тех, значения в которых известны, тем более модель не уверена в том, какое значение функции в этой точке, и тем шире доверительный интервал. Наоборот, в точках, где значения известны, доверительный интервал имеет нулевой радиус.

image.png
На основе источника

Байесовская оптимизация в общем случае представляет собой следующий алгоритм. Пусть StS_t​ — множество предыдущих наблюдений целевой функции f:(f(x1),...,f(xt))f: (f(x_1),...\,,f(x_t)), а α()\alpha(\cdot) — некоторая acquisition function.

  • На итерации t+1t+1 вычисляется точка xt+1x_{t+1}, в которой нужно провести следующее вычисление целевой функции:

    xt+1=argmaxxXα(xSt).x_{t+1} = \arg \max_{x \in X} \alpha(x|S_t).

  • Вычисляется значение f(xt+1)f(x_{t+1}) и обновляется множество наблюдений St+1=(St,f(xt+1))S_{t+1} = (S_t,f(x_{t+1})).

  • Обновляется статистическая модель.

Чтобы такой алгоритм работал эффективно, α\alpha должна быть легко вычислимой и дифференцируемой.

На рисунке ниже изображены три итерации этого алгоритма. Здесь пунктирная линия — это целевая функция, сплошная линия — график среднего вероятностной модели, жёлтым цветом обозначен доверительный интервал модели.

Серый график снизу — это график acquisition function. Её значения велики там, где вероятностная модель предсказывает большие значения целевой функции (exploitation), и там, где велика неуверенность вероятностной модели (exploration).

На каждой итерации находится точка максимума acquisition function (чёрный крестик), и следующая итерация произойдёт в этой точке (серый кружок на графике функции). На нижнем графике побеждает exploitation, так как acquisition function верно предсказала, что наблюдения из неизвестных областей слабо повлияют на нашу текущую оценку максимума ff.

image.png
На основе источника

Байесовская оптимизация хорошо работает, когда нужно оптимизировать небольшое число гиперпараметров, так как в наивной реализации алгоритм не поддаётся распараллеливанию. При большой размерности пространства гиперпараметров скорость сходимости не лучше, чем у обычного Random Search (как утверждается в этой статье).

Байесовская оптимизация в изначальной постановке предполагалась для работы с непрерывными гиперпараметрами, а для работы с категориальными гиперпараметрами ей нужны некоторые трюки:

  1. Если нужно найти оптимальное значение только одного гиперпараметра и этот параметр категориальный, то можно, например, использовать семплирование Томпсона (как тут, в разделе Beta-Bernoulli bandit). Вообще проблему выбора наилучшего значения категориального гиперпараметра можно переформулировать как проблема многорукого бандита (англ. multi-armed bandit problem) и использовать любой известный способ решения этой задачи.

  2. Если категориальных гиперпараметров больше одного и кроме них есть некатегориальные, то:

    • можно попробовать использовать специальные виды ядер в гауссовских процессах, как, например, сделано здесь;
    • можно заменить гауссовские процессы на Random Forest (подробнее можно посмотреть здесь, в разделе Random forests).

Полезные ссылки

А если вам интересно как следует разобраться в байесовской оптимизации (в частности, рассмотреть больше примеров вероятностных моделей и разных acquisition function), то вот полезный контент:

Алгоритм TPE

TPE расшифровывается как Tree-structured Parzen Estimator (древесно-структурированная оценка Парзена).

Этот алгоритм, как и алгоритм байесовской оптимизации, итерационный: на каждой итерации принимается решение о том, какие следующие значения гиперпараметров нужно выбрать, исходя из результатов предыдущих итераций. Но идейно имеет довольно сильные отличия.

Предположим сначала, что мы хотим сделать поиск оптимального значения для одного гиперпараметра.

На нескольких первых итерациях алгоритму требуется разогрев: нужно иметь некоторую группу значений данного гиперпараметра, на которой известно качество модели. Самый простой способ собрать такие наблюдения — провести несколько итераций Random Search (количество итераций определяет пользователь).

Следующим шагом будет разделение собранных во время разогрева данных на две группы. В первой группе будут те наблюдения, для которых модель продемонстрировала лучшее качество, а во второй — все остальные. Размер доли лучших наблюдений задаёт пользователь: чаще всего это 10–25% от всех наблюдений. Картинка ниже иллюстрирует такое разбиение:

image.png
Источник

Далее некоторым образом строятся оценки распределения (x)\ell(x) лучших наблюдений и распределения g(x)g(x) всех остальных в пространстве значений рассматриваемого гиперпараметра.

О том, как оцениваются (x)\ell(x) и g(x)g(x)

Если гиперпараметр принимает непрерывные значения, то распределения (x)\ell(x) и g(x)g(x) можно оценить на основе Parzen window density estimation. Идея данного метода в следующем.

Пусть у нас имеются точки x1,,xnx_1, \dots, x_n​, которые были насемплированы из некоторого неизвестного распределения ff. Нам нужно каким-то образом оценить ff по известным данным. Для этого каждое наблюдение xix_i ​помещается в центр некоторого симметричного распределения KK с дисперсией hh, а оценкой для ff становится смесь этих распределений:

f^h(x)=1nhi=1nK(xxih)\hat{f}_h(x) = \frac{1}{nh} \sum_{i=1}^{n} K \bigg( \frac{x-x_i}{h} \bigg)

Распределения KK обычно называют ядрами, примеры ядер можно найти тут. На картинке ниже показана зависимость вида итогового распределения от параметра hh (который часто называют bandwidth):

image.png
Источник

Чем больше у нас наблюдений, тем точнее можем оценить целевое распределение:

image.png
Источник

Если гиперпараметр категориальный и принимает значения c1,,cnc_1, \dots, c_n​, то в качестве (x)\ell(x) и g(x)g(x) можно задать категориальные распределения в виде наборов из nn вероятностей (p1,,pn)(p_1, \dots, p_n), где pip_i соответствует вероятности насемплировать значение cic_i​. Значения pip_i для (x)\ell(x) будут пропорциональны числу раз, которое каждое из значений cic_i​ встретилось в группе лучших наблюдений (и, соответственно, худших наблюдений в случае g(x)g(x)).

Например, пусть у гиперпараметра всего 3 значения и уже прошло 60 итераций алгоритма. Пусть среди лучших 15 испытаний 2 раза встретилось значение c1c_1, 5 раз — значение c2c_2 и 8 раз — c3c_3​.

Тогда (x)(p1=215,p2=515,p3=815)\ell(x) \approx \big(p_1 = \frac{2}{15}, p_2 = \frac{5}{15}, p_3 = \frac{8}{15}\big). Аналогично будет строиться g(x)g(x).

На следующем шаге алгоритма мы семплируем несколько значений-кандидатов из распределения (x)\ell(x) (количество таких семплирований тоже задаёт пользователь, можно задать их число равным, например, 1000). Из насемплированных кандидатов мы хотим найти тех, кто с большей вероятностью окажется в первой группе (состоящей из лучших наблюдений), чем во второй. Для этого для каждого кандидата xx вычисляется ожидаемое улучшение (англ. Expected Improvement):

EI(x)=(x)g(x)EI(x)=\frac{\ell(x)}{g(x)}

Замечание. На самом деле стоит отметить, что в оригинальной статье величина EIEI имеет более общее определение. Но там же доказывается, что максимизация EIEI в исходном определении эквивалентна максимизации отношения выше.

Кандидат с наибольшим значением EI(x)EI(x) будет включён во множество рассматриваемых гиперпараметров на следующей итерации:

image.png
Источник

После того как было выбрано значение-кандидат, максимизирующее EIEI, обучается модель с этим значением гиперпараметра. После обучения мы замеряем её качество на валидационной выборке и в соответствии с этим результатом обновляем распределения (x)\ell(x) и g(x)g(x): снова ранжируются все имеющиеся кандидаты по качеству модели с учётом последнего, из топ-10–25% формируется обновлённое (x)\ell(x), из остальных — g(x)g(x). Так происходит столько раз, сколько итераций алгоритма мы задали.

Теперь опишем, как алгоритм работает в общем случае, когда гиперпараметров более одного. Алгоритм работает с гиперпараметрами, представляя их в форме дерева (отсюда tree в названии). Например, в документации библиотеки Hyperopt можно увидеть такой пример:

1from hyperopt import hp
2 
3space = hp.choice('classifier_type', [
4    {
5        'type': 'naive_bayes',
6    },
7    {
8        'type': 'svm',
9        'C': hp.lognormal('svm_C', 0, 1),
10        'kernel': hp.choice('svm_kernel', [
11            {'ktype': 'linear'},
12            {'ktype': 'RBF', 'width': hp.lognormal('svm_rbf_width', 0, 1)},
13            ]),
14    },
15    {
16        'type': 'dtree',
17        'criterion': hp.choice('dtree_criterion', ['gini', 'entropy']),
18        'max_depth': hp.choice('dtree_max_depth',
19            [None, hp.qlognormal('dtree_max_depth_int', 3, 1, 1)]),
20        'min_samples_split': hp.qlognormal('dtree_min_samples_split', 2, 1, 1),
21    },
22])

На рисунке ниже изображено дерево, соответствующее данному примеру:

image

Корень дерева ε\varepsilon — фиктивная вершина, введённая для удобства. Здесь первый уровень дерева — выбор классификатора (наивный байес, SVM, решающее дерево). Дальнейшие уровни — гиперпараметры самих классификаторов и зависящие уже от них гиперпараметры (например, SVM \rightarrow kernel \rightarrow RBF \rightarrow width). Движение по дереву во время итераций алгоритма происходит по некоторому пути от корня к листу и обратно вдоль пройденного пути (этот процесс подробнее описан ниже).

Под некоторыми вершинами записан набор гиперпараметров в скобках (например, kernel и C под SVM). Это означает, что при приходе в эту вершину значения всех гиперпараметров, перечисленных в скобках, должны быть так или иначе выбраны.

С каждой вершиной дерева, в которой будет происходить семплирование значений, сопоставляется своя пара (x)\ell(x) и g(x)g(x) с учётом значений, насемплированных на этапе «разогрева». Каждому гиперпараметру, перечисленному в скобках, соответствует своя собственная пара. Если из названия гиперпараметра не идут стрелки (например, C у SVM и min_samples_split у Decision Tree), то это означает, что от его значения не зависят значения никаких других гиперпараметров.

Поэтому либо будет выбрано его значение, максимизирующее EIEI для соответствующих ему \ell и gg, либо уже ничего не нужно семплировать (как, например, в вершинах linear или gini). Если же из гиперпараметра идут стрелки на следующий уровень, то с помощью максимизации EIEI будет выбрано, в каком направлении сделать переход. Например, из корня ε\varepsilon выбирается, какой классификатор рассмотреть на следующем этапе, а из параметра kernel можно перейти либо к RBF, либо к linear.

Теперь опишем сам алгоритм. Сначала так же, как и в одномерном случае, происходит «разогрев»: проводится некоторое количество итераций Random Search с теми изначальными распределениями, которые были заданы для гиперпараметров (в примере из Hyperopt эти распределения задаются как hp.qlognormal, hp.lognormal и так далее). Затем начинается итерационное обновление дерева гиперпараметров. Обновление дерева на каждой итерации происходит в два этапа.

Первый этап. Сначала алгоритм идёт из корня дерева до некоторого листа. В каждой вершине для каждого соответствующего ей гиперпараметра он находит значение, максимизирующее EIEI.

Если выбор значения для некоторого гиперпараметра означает переход на следующий уровень дерева, он идёт в ту вершину, которая соответствует максимизации EIEI.

Так он идёт до тех пор, пока не упрётся в какой-то лист. Пройденный путь от корня до листа задаёт полный набор значений гиперпараметров для модели, и её с этими значениями можно провалидировать.

Пример

Пусть вы находитесь в корне ε\varepsilon и выбираете классификатор. Допустим, классификатор SVM оказался оптимальным по критерию EIEI. Вы переходите в соответствующую ему вершину, и здесь вам нужно провести семплирование значений для двух гиперпараметров — kernel и C.

Для C вы выбираете некоторое значение, которое максимизирует EIEI. Пусть оно оказалось равно 0,10,1. А для kernel вы с помощью максимизации EIEI выбираете, в какую вершину на следующем уровне вы отправитесь. Пусть эта вершина — RBF. Для него вы семплируете конкретное значение — width. Пусть оно оказалось равным 0,90,9.

Получилось, что вы прошли полный путь и получили модель с заданным набором гиперпараметров, которую теперь можно провалидировать:

SVM(C=0,1,kernel=RBF(width=0,9))\text{SVM}(C = 0,1, \text{kernel} = \text{RBF}(\text{width} = 0,9))

Второй этап. После того как модель, полученная на предыдущем этапе, была провалидирована, распределения в вершинах дерева нужно обновить в соответствии с информацией о полученном качестве.

Для этого алгоритм поднимается из листа наверх, обновляя распределения во всех вершинах дерева вдоль своего пути. В каждой вершине для каждого гиперпараметра процедура обновления та же, что была описана для одного гиперпараметра: имеющиеся значения гиперпараметров переранжируются по качеству с учётом результата последнего кандидата (этот результат общий для всех вершин вдоль пути), по топ-10–25% оценивается (x)\ell(x), по остальным — g(x)g(x).

В качестве окончательного ответа алгоритм выдаёт набор гиперпараметров (или, как в примере выше, не только гиперпараметры, но даже саму модель), на котором было получено лучшее качество за все итерации. Число итераций алгоритма задаёт пользователь.

За дальнейшими деталями о процедуре обновления дерева для алгоритма TPE можно обратиться к этой статье и к исходному коду алгоритма TPE из библиотеки Hyperopt.

Стоит заметить, что если гиперпараметры не лежат вместе ни в одном пути в дереве, то TPE считает их независимыми. Это недостаток данного алгоритма, так как некоторые гиперпараметры, находящиеся по смыслу в разных путях в дереве, зависят от друг от друга.

Например, с регуляризацией мы можем тренировать нейросеть большее число эпох, чем без регуляризации, потому что без регуляризации сеть на большом числе эпох может начать переобучаться. В этом конкретном примере можно использовать такой трюк:

1hp.choice(
2  'training_parameters', [
3    {
4        'regularization': True,
5        'n_epochs': hp.quniform('n_epochs', 500, 1000, q=1),
6    },
7    {
8        'regularization': False,
9        'n_epochs': hp.quniform('n_epochs', 20, 300, q=1),
10    },
11])

Но если внутренние зависимости между гиперпараметрами вам неизвестны, то алгоритм не сможет найти их сам.

Критерий EIEI позволяет методу TPE балансировать между exploration и exploitation. Семплирование из распределения (x)\ell(x) — это, с одной стороны, exploitation, так как гиперпараметры, семплируемые из него, близки к оптимуму, но это же привносит элемент exploration, так как семплируемые гиперпараметры не равны оптимуму в точности.

Полезные ссылки

Для дальнейшего изучения метода TPE можно использовать следующие источники:

  • Оригинальная статья, в которой предложены методы TPE и байесовская оптимизация.

  • Блог-пост про TPE и остальные методы тюнинга гиперпараметров от NeuPy. Там же можно найти пример применения TPE из Hyperopt.

  • Отличное объяснение того, что такое метод парзеновского окна.

  • Отличный туториал по различным методам оптимизации гиперпараметров (который упомянут выше, в разделе про байесовскую оптимизацию).

Метод PBT

Population Based Training (PBT, популяционное обучение) использует идеи из теории эволюционных стратегий и с самого начала включает параллельные вычисления.

Методы, описанные выше, имеют свои сильные и слабые стороны.

  • Grid Search и Random Search:

    • отлично параллелизуются;

    • не используют результаты предыдущих итераций.

  • Байесовская оптимизация и TPE:

    • трудно параллелизуются;

    • используют результаты предыдущих итераций; при сходимости результаты лучше, чем у Random Search и Grid Search.

В алгоритме PBT была сделана попытка объединить сильные стороны обеих групп, что проиллюстрировано на картинке ниже:

image.png
Источник

В процессе работы алгоритм обучает не одну модель, а целую популяцию P\mathcal{P}-моделей — набор моделей одинакового типа, различающихся только набором гиперпараметров:

P={(θi,hi)i=1,,N},\mathcal{P} = \{(\theta_i,h_i)\,|\,i=1,\dots,N \},

где θi\theta_i​ и hih_i​ — веса и гиперпараметры модели ii соответственно.

Предполагается также, что модели обучаются как-то итерационно, например градиентным спуском (но могут использоваться и безградиентные методы, такие как эволюционные стратегии). Изначально каждая модель в популяции имеет случайные веса и гиперпараметры. Каждая модель из популяции тренируется параллельно с остальными, и периодически качество каждой модели замеряется независимо от остальных.

Как только какая-то модель считается созревшей для обновления (например, прошла достаточное число шагов градиентного спуска или преодолела некоторый порог по качеству), у неё появляется шанс быть обновлённой относительно всей остальной популяции:

  • процедура exploit(): если у модели низкое качество относительно популяции, то её веса заменяются на веса модели с более высоким качеством;

  • процедура explore(): если веса модели были перезаписаны, шаг explore добавляет случайный шум в параметры модели.

При таком подходе только лучшие пары моделей и гиперпараметров выживут и будут обновляться, что позволяет добиться более высокой утилизации ресурсов.

image.png
Источник

Стоит отметить, что наиболее оптимальный размер популяции, выявленный авторами в результате экспериментов, — от 20 до 40, что довольно много и не реализуется на обычном ноутбуке.

Красивая гифка с демонстрацией работы алгоритма:

gif.png
Источник

Полезные ссылки

Опенсорс-библиотеки

На практике для подбора гиперпараметров используются библиотечные реализации.

Ниже — краткий обзор актуальных решений как на основе перебора по сетке, так и с применением более продвинутых методов вроде адаптивного TPE.

Scikit-learn

В библиотеке Scikit-learn есть реализации Grid Search и Random Search, что очень удобно, если вы используете модели из sklearn. Примеры их использования можно найти здесь.

Hyperopt

В библиотеке Hyperopt реализованы три метода оптимизации гиперпараметров:

У них есть небольшой туториал по тому, как начать пользоваться библиотекой. Кроме того, у них есть обёртка над sklearn, позволяющая работать с моделями оттуда: Hyperopt-sklearn.

Optuna

В библиотеке Optuna реализованы те же методы оптимизации, что и в Hyperopt, но по многим параметрам она оказывается удобнее. Хорошее сравнение Optuna и Hyperopt можно найти здесь.

Scikit-Optimize

В библиотеке Scikit-Optimize реализованы алгоритмы байесовской оптимизации и Random Search. Кроме самих методов оптимизации библиотека предоставляет отличный инструментарий для различных визуализаций. Хорошее описание возможностей библиотеки можно найти тут.

Keras Tuner

Библиотека Keras Tuner позволяет подбирать гиперпараметры для нейросеток, написанных на TensorFlow 2.0, и для обычных моделей из Scikit-learn. Доступные методы оптимизации — Random Search и Hyperband. Хороший гайд по использованию данной библиотеки можно найти тут.

Заключение

Список описанных методов не исчерпывает все существующие на данный момент методы оптимизации гиперпараметров: остались за кадром такие алгоритмы, как ASHA, Hyperband, BOHB. Хороший сравнительный обзор этих трёх алгоритмов можно найти здесь.

Мы собрали все описанные выше алгоритмы в таблицу, чтобы вам было удобнее сравнивать их между собой. А к некоторым оставили дополнительные комментарии.

Алгоритм

Сильные стороны

Слабые стороны

Grid Search

  • Самый простой для понимания и реализации

  • Тривиально распараллеливается

  • Не использует результаты других итераций

  • Ограничен в выборе заданной сеткой

  • Долго работает, если делает последовательный перебор по сетке

  • Нет гарантии необходимого числа итераций

Random Search

  • Позволяет находить оптимальные гиперпараметры эффективнее, чем Grid Search, в частности благодаря тому, что непрерывные параметры можно задать в виде распределения, а не перечислять значения заранее

  • Тривиально распараллеливается

  • Допускает усиление за счёт использования квазислучайных распределений при семплировании

  • Не использует результаты других итераций

  • Ограничен в выборе заданной сеткой, хотя в некоторых случаях менее жёстко, чем Grid Search

Байесовская оптимизация

  • Использует результаты предыдущих итераций

  • Может моделировать внутренние зависимости между гиперпараметрами (за счёт работы с ними в едином подмножестве Rn\mathbb{R}^n, где nn — число гиперпараметров)

  • Может расширять заданные изначально границы множества поиска гиперпараметров

  • Достигает более высокого качества, чем Random Search, если удалось провести достаточное количество итераций

  • Параллелится нетривиально

  • В нераспараллеленном случае работает долго, так как для каждой итерации заново строит вероятностную модель. В случае если такая модель — гауссовские процессы, сложность получается порядка n3n^3, где nn — число гиперпараметров

  • Для работы с категориальными гиперпараметрами нужны нетривиальные хаки

Tree-structured Parzen Estimator

  • Использует результаты предыдущих итераций

  • Может работать с зависимостями между гиперпараметрами, в которых один гиперпараметр не будет рассматриваться, если другой не примет какое-то определённое значение (например, число нейронов во втором слое нейросети нужно перебирать, если параметр «число слоёв» имеет значение не менее двух)

  • Имеет линейную сложность по числу гиперпараметров (в отличие от байесовской оптимизации)

  • Не требует специальных хаков для работы с категориальными признаками, так как каждый гиперпараметр в этом алгоритме имеет своё отдельное одномерное распределение и не нужно строить сложное совместное распределение всех гиперпараметров (как в байесовской оптимизации)

  • Достигает высоких результатов по качеству, довольно часто используется в соревнованиях

  • Не может моделировать неявные зависимости между гиперпараметрами (те, которые юзер не задал с помощью дерева)

  • Хотя сложность и меньше, чем у байесовской оптимизации, может работать довольно медленно даже на не очень большом числе гиперпараметров

Population Based Training

  • Параллельный by design

  • Может использовать результаты предыдущих итераций

  • Для эффективной работы нужно много воркеров (от 20 до 40), что нетривиально для реализации

Предлагаем выполнить лабораторную работу: ссылка.

А в следующем параграфе мы подведём итоги всей главы: что вы узнали, чему научились и как применять эти знания на практике.

Чтобы добавить в заметки выделенный текст, нажмите Command + E
Предыдущий параграф3.3. Кросс-валидация

Как строить надёжные оценки качества моделей и никогда не смешивать train и test

Следующий параграф4.1. Вероятностный подход в ML

Как описать привычные модели на языке статистики. Оптимизация функции потерь vs оценка максимального правоподобия

Вступайте в сообщество хендбука

Здесь можно найти единомышленников, экспертов и просто интересных собеседников. А ещё — получить помощь или поделиться знаниями.